package 简单.二分查找;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定两个数组，编写一个函数来计算它们的交集
 * <p>
 * 来源：https://leetcode-cn.com/problems/intersection-of-two-arrays/
 */
public class 两个数组的交集_349 {

    public static void main(String[] args) {

        int[] x = {2};
        int[] y = {2};
        int[] intersection = intersection2(x, y);
        System.out.println(intersection[0]);


    }

    //二分法
    public static int[] intersection1(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        //从0开始
        for (int i = 0; i <= nums2.length - 1; i++) {
            int left = 0;
            int right = nums1.length - 1;
            int target = nums2[i];
            while (right >= left) {
                int mid = left + (right - left) / 2;
                if (nums1[mid] == target) {
                    set.add(nums1[mid]);
                    //找到之后需要跳出当前循环，否则死循环
                    break;
                } else if (nums1[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        int index = 0;
        int[] ints = new int[set.size()];
        for (Integer integer : set) {
            ints[index++] = integer;
        }
        return ints;
    }

    //利用Set，时间复杂度O(m+n),空间复杂度0(m+n),取决于两个数组的长度
    public static int[] intersection2(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        Set<Integer> set = new HashSet<>();

        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            set2.add(i);
        }

        for (Integer i : set1) {
            if (set2.add(i) == false) {
                set.add(i);
            }
        }

        int index = 0;
        int[] ints = new int[set.size()];
        for (Integer integer : set) {
            ints[index++] = integer;
        }
        return ints;
    }

    //双指针


}
